package org.apache.commons.graph.algorithms.scc.sample

import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.algorithms.scc.SccAlgorithm
import org.apache.commons.graph.model.RevertedGraph
import org.apache.commons.graph.utils.Assertions

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Implements the classical Kosaraju's algorithm to find the strongly connected components
 *
 * @param <V> the Graph vertices type.
 * @param <E> the Graph edges type.
 * @param <G> the directed graph type
</G></E></V> */
/**
 * Create a new [KosarajuSharirAlgorithm] instance for the given [org.apache.commons.graph.Graph].
 *
 * @param graph the [org.apache.commons.graph.Graph] on which to apply the algorithm
 */
internal class KosarajuSharirAlgorithm<V, E>(
    private val graph: DirectedGraph<V, E>
) : SccAlgorithm<V> {
    /**
     * Performs a depth-first search to create a recursive vertex list.
     *
     * @param source the starting vertex
     * @param visitedVertices a [Set] containing all visited vertices
     * @return the recursively expanded vertex list for Kosaraju's algorithm
     */
    private fun getExpandedVertexList(source: V?, visitedVertices: MutableSet<V>): MutableList<V> {
        val size = if (source != null) 13 else graph.order
        val vertices: MutableSet<V> = HashSet(size)

        if (source != null) {
            vertices.add(source)
        } else {
            for (vertex in graph.vertices) {
                vertices.add(vertex)
            }
        }

        // use an ArrayList so that subList is fast
        val expandedVertexList = ArrayList<V>()

        var idx = 0
        while (vertices.isNotEmpty()) {
            // get the next vertex that has not yet been added to the expanded list
            val v = vertices.iterator().next()
            searchRecursive(graph, v, expandedVertexList, visitedVertices, true)
            // remove all expanded vertices from the list of vertices that have to be
            // still processed. To improve performance, only the items that have been
            // added to the list since the last iteration are removed
            vertices.removeAll(expandedVertexList.subList(idx, expandedVertexList.size))
            idx = expandedVertexList.size
        }

        return expandedVertexList
    }

    /**
     * Applies the classical Kosaraju's algorithm to find the strongly connected components.
     *
     * @return the input graph strongly connected component.
     */
    override fun perform(): Set<Set<V>> {
        val visitedVertices: MutableSet<V> = HashSet()
        val expandedVertexList: List<V> = getExpandedVertexList(null, visitedVertices)
        val reverted: DirectedGraph<V, E> = RevertedGraph(graph)

        val sccs: MutableSet<Set<V>> = HashSet()

        // insert the expanded vertices in reverse order into a linked hash set
        // this is needed to quickly remove already found SCCs from the stack
        val stack = LinkedHashSet<V>()
        for (i in expandedVertexList.indices.reversed()) {
            stack.add(expandedVertexList[i])
        }

        while (stack.isNotEmpty()) {
            // remove the last element from the expanded vertices list
            val v = stack.iterator().next()
            val sccSet: MutableSet<V> = HashSet()
            searchRecursive(reverted, v, sccSet, visitedVertices, false)

            // remove all strongly connected components from the expanded list
            stack.removeAll(sccSet)
            sccs.add(sccSet)
        }

        return sccs
    }

    /**
     * Applies the classical Kosaraju's algorithm to find the strongly connected components of
     * a vertex `source`.
     *
     * @param source the source vertex to start the search from
     * @return the input graph strongly connected component.
     */
    fun perform(source: V): Set<V> {
        Assertions.checkNotNull(
            source,
            "Kosaraju Sharir algorithm cannot be calculated without expressing the source vertex"
        )
        Assertions.checkState(graph.containsVertex(source), "Vertex %s does not exist in the Graph", source)

        val visitedVertices: MutableSet<V> = HashSet()
        val expandedVertexList = getExpandedVertexList(source, visitedVertices)
        val reverted: DirectedGraph<V, E> = RevertedGraph(graph)

        // remove the last element from the expanded vertices list
        val v = expandedVertexList.removeAt(expandedVertexList.size - 1)
        val sccSet: MutableSet<V> = HashSet()
        searchRecursive(reverted, v, sccSet, visitedVertices, false)
        return sccSet
    }

    /**
     * Searches a directed graph in iterative depth-first order, while adding the visited
     * vertices in a recursive manner, i.e. a vertex is added to the result list only
     * when the search has finished expanding the vertex (and its subsequent childs).
     *
     *
     * **Implementation Note:** in the first step we look for vertices that have not
     * been visited yet, while in the second step we search for vertices that have already
     * been visited.
     * @param g the graph to be search
     * @param source the start vertex
     * @param coll the recursive collection of visited vertices
     * @param visited contains vertices that have been already visited
     * @param forward `true` for the first step of Kosaraju's algorithm,
     * `false` for the second step.
     */
    private fun searchRecursive(
        g: DirectedGraph<V, E>, source: V,
        coll: MutableCollection<V>, visited: MutableSet<V>,
        forward: Boolean
    ) {
        val stack = linkedSetOf<V>()
        stack.addLast(source)

        while (stack.isNotEmpty()) {
            val v = stack.removeLast()

            // if the vertex has already been visited it can be put into the
            // collection, as we are now finished expanding this vertex
            // the if takes both cases into account:
            //  * step1: forward && visited.contains(v)
            //  * step2: !forward && !visited.contains(v)
            if (!(forward xor visited.contains(v))) {
                coll.add(v)
                continue
            }

            // add the current vertex to the stack, so it is visited again
            // when all connected vertices have been visited
            stack.addLast(v)
            if (forward) {
                visited.add(v)
            } else {
                visited.remove(v)
            }

            // add all not yet visited vertices that can be reached from this
            // vertex to the stack
            for (w in g.getOutbound(v)) {
                if (!(forward xor !visited.contains(w))) {
                    stack.addLast(w)
                }
            }
        }
    }
}

fun<V, E> SccAlgorithm.Companion.kosarajuSharirAlgorithm(graph: DirectedGraph<V, E>):SccAlgorithm<V> = KosarajuSharirAlgorithm(graph)